export type ReferMap = {
  [key: string]: string[];
};

/**
 * 找出所有最小环
 * @param referMap 引用映射
 * @returns 所有最小环
 */
export function findCirclePath(referMap: ReferMap): string[][] {
  const cycles: string[][] = [];
  const visited = new Set<string>();
  const recursionStack = new Set<string>();
  const pathStack: string[] = [];

  function dfs(node: string): void {
    if (recursionStack.has(node)) {
      // Found a cycle, extract the cycle path
      const cycleStartIndex = pathStack.indexOf(node);
      if (cycleStartIndex !== -1) {
        const cycle = pathStack.slice(cycleStartIndex);
        cycle.push(node); // Complete the cycle
        
        // Check if this is a minimal cycle (not contained in existing cycles)
        const isMinimal = !cycles.some(existingCycle => 
          cycle.length > existingCycle.length && 
          existingCycle.every(node => cycle.includes(node))
        );
        
        if (isMinimal) {
          // Normalize cycle to start with the lexicographically smallest node
          const minNode = Math.min(...cycle.slice(0, -1).map((node, index) => ({ node, index }))
            .sort((a, b) => a.node.localeCompare(b.node))
            .map(item => item.index));
          const normalizedCycle = [
            ...cycle.slice(minNode, -1),
            ...cycle.slice(0, minNode),
            cycle[minNode] // Complete the cycle
          ];
          
          // Check if we already have this cycle (in any rotation)
          const cycleKey = normalizedCycle.slice(0, -1).join('->');
          const isDuplicate = cycles.some(existingCycle => {
            const existingKey = existingCycle.slice(0, -1).join('->');
            return cycleKey === existingKey;
          });
          
          if (!isDuplicate) {
            cycles.push(normalizedCycle);
          }
        }
      }
      return;
    }

    if (visited.has(node)) {
      return;
    }

    visited.add(node);
    recursionStack.add(node);
    pathStack.push(node);

    const dependencies = referMap[node] || [];
    for (const dependency of dependencies) {
      dfs(dependency);
    }

    recursionStack.delete(node);
    pathStack.pop();
  }

  // Start DFS from each unvisited node
  for (const node in referMap) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return cycles;
}